package dp;

import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.concurrent.ForkJoinPool;
import java.util.function.DoublePredicate;

/**
 * @Author: wangliuyang
 * @Date: 2021/8/16 12:42
 * @Description:分割回文字符串
 */
public class StringPartition {
    public List<List<String>> partition(String s) {
/*
        Boolean[][] help = generatePalindromeDB(s);
        int[] db = new int[s.length()];//db[i]表示i-i之间字符串能够分割种数；
        db[s.length() - 1] = 1;
        for (int i = s.length() - 2; i >= 0; i--){
            for (int j = i; j < s.length(); j++) {
                if (help[i][j]){
                    db[i] += j == s.length()-1 ? 0 : db[j + 1];
                }
            }
        }
        return db[0];//求解的为能产生多少种
*/
        boolean[][] help = generatePalindromeDB(s);
        List<List<String>> ans = new LinkedList<>();
        dfs(ans,new LinkedList(),0,s,help);
        return ans;
    }
    public void dfs(List ans,LinkedList path,int index,String s,boolean[][] help){
        if (index == s.length()){
            ans.add(new LinkedList<String>(path));
            return;
        }
        for (int i = index; i < s.length(); i++) {
            if (help[index][i]){
                path.add(s.substring(index,i+1));
                dfs(ans,path,i+1,s,help);
                path.removeLast();
            }
        }
    }
    public boolean[][] generatePalindromeDB(String s){
        int N = s.length();
        boolean[][] db = new boolean[N][N];//数组含义，i-j索引间字符串是否为回文
        for (int i = 0; i < db.length; i++) {
            db[i][i] = true;
        }
        for (int i = 0; i < db.length - 1; i++) {
            db[i][i+1] = s.charAt(i) == s.charAt(i+1);
        }
        for (int i = N - 3; i>=0; i--){
            for (int j = i + 2;j<N; j++){
                db[i][j] = s.charAt(i) == s.charAt(j) ? db[i+1][j-1] : false;
            }
        }
        return db;
    }
}
